package com.company;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * @date : 2022/2/10 13:49
 * leetcode面试算法题：排序循环链表增加一个元素
 * https://leetcode.cn/problems/4ueAj6/
 * 这题写的还是有问题，力扣题目表述是 “给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。”
 */

public class P016_ListNode {
    public static void main(String[] args) {
        ListNode node = new ListNode(3);
        ListNode head = new ListNode(4, new ListNode(1, new ListNode(2, node)));
        node.next = head;
        Set<ListNode> set = new HashSet<>();
        set.add(head);
        System.out.println(head.val);
        while (set.add(head.next)) {
            head = head.next;
            System.out.println(head.val);
        }
        head = head.next;
        System.out.println("-----------");
        ListNode ans = insertListNode3(head, 1);
//        ListNode ans = head;
        set = new HashSet<>();
        set.add(ans);
        System.out.println(ans.val);
        while (set.add(ans.next)) {
            ans = ans.next;
            System.out.println(ans.val);
        }

    }

    // 改写：指针还指向原来的元素(这个答案还是有问题)
    public static ListNode insertListNode3(ListNode head, int val) {
        if (head == null) {
            ListNode ans = new ListNode(val);
            ans.next = ans;
            return ans;
        }
        int num = head.val;
//        System.out.println("num = " + num);
        List<Integer> list = new ArrayList<>();
        Set<ListNode> set = new HashSet<>();
        set.add(head);
        while (set.add(head.next)) {
            list.add(head.val);
            head = head.next;
        }
        list.add(head.val);
        list.add(val);
        Collections.sort(list);
        ListNode ans = new ListNode(list.get(0));
        ListNode dummy = ans;
        for (int i = 1; i < list.size(); i++) {
            dummy.next = new ListNode(list.get(i));
            dummy = dummy.next;
        }
        dummy.next = ans;
        while (ans.next.val != num) {
            ans = ans.next;
        }
        return ans.next;
    }

    // 思路：用Set判断循环，用List放数据，新增数据后，重新组装链表
    public static ListNode insertListNode(ListNode head, int val) {
        List<Integer> list = new ArrayList<>();
        Set<ListNode> set = new HashSet<>();
        set.add(head);
        while (set.add(head.next)) {
            list.add(head.val);
            head = head.next;
        }
        list.add(head.val);
        list.add(val);
        Collections.sort(list);
        ListNode ans = new ListNode(list.get(0));
        ListNode dummy = ans;
        for (int i = 1; i < list.size(); i++) {
            dummy.next = new ListNode(list.get(i));
            dummy = dummy.next;
        }
        dummy.next = ans;
        return ans;
    }

    public static class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    ", next=" + next +
                    '}';
        }
    }
}